package com.jwetherell.my.problems.patternsearching;

/**
 * http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
 * 
 * We have discussed Naive pattern searching algorithm in the previous post. The
 * worst case complexity of Naive algorithm is O(m(n-m+1)). Time complexity of
 * KMP algorithm is O(n) in worst case.
 * 
 * 
 * 
 * @author yatendra
 * 
 */
public class KMP_Knuth_Morris_Pratt_PatternSearch {

	public static void main(String[] args) {
		String textStr = "AABAACAADAABAAABAA";
		String patternStr = "AABA";

		// String textStr = "AAAAAAAAAAAAAAAAAA";
		// String patternStr = "AAAAA";

		// String textStr = "AAAAAAAAAAAAAAAAAB";
		// String patternStr = "AAAAAB";

		System.out.println("Text: " + textStr);
		System.out.println("Pattern: " + patternStr);

		char[] text = textStr.toCharArray();
		char[] pattern = patternStr.toCharArray();

		KMP_Knuth_Morris_Pratt_PatternSearch patternSearch = new KMP_Knuth_Morris_Pratt_PatternSearch();
		int[] lpsArray = patternSearch.computeLPSArray(pattern);
		patternSearch.printPatternIndices(text, pattern, lpsArray);
	}

	/**
	 * Examples:
	 * 
	 * For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
	 * 
	 * For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
	 * 
	 * For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
	 * 
	 * For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
	 * 
	 * For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
	 * 
	 */
	private int[] computeLPSArray(char[] pattern) {
		int[] lpsArray = new int[pattern.length];

		for (int i = 0; i < pattern.length; i++) {
			int j = 0;
			int k = 1;
			int lpsValue = 0;

			while (k <= i) {
				if (pattern[j] == pattern[k]) {
					lpsValue++;
					j++;
					k++;
				} else {
					j = 0;
					k -= lpsValue - 1;
					lpsValue = 0;
				}
			}

			lpsArray[i] = lpsValue;
		}

		return lpsArray;
	}

	private void printPatternIndices(char[] text, char[] pattern, int[] lpsArray) {
		System.out.print("LCS Array: ");
		for (int i = 0; i < lpsArray.length; i++)
			System.out.print(lpsArray[i] + " ");
		System.out.println("\n");

		int i = 0;
		int j = 0;

		while (i < text.length - pattern.length + 1) {

			if (text[i] == pattern[j]) {
				i++;
				j++;
			} else {
				if (j != 0) // check b'coz j-1 will be -1 if j==0
					j = lpsArray[j - 1];
				else
					i++;
			}

			if (j == pattern.length) {
				System.out.println("Pattern found at index " + (i - j));
				j = lpsArray[j - 1];
			}

		}
	}

	// private void printPatternIndices(char[] text, char[] pattern, int[]
	// lpsArray) {
	// for (int i = 0; i < lpsArray.length; i++)
	// System.out.print(lpsArray[i] + " ");
	//
	// int i = 0; // index for txt[]
	// int j = 0; // index for pat[]
	//
	// while (i < text.length) {
	// if (pattern[j] == text[i]) {
	// j++;
	// i++;
	// }
	//
	// if (j == pattern.length) {
	// System.out.println("Found pattern at index " + (i-j) + "\n");
	// j = lpsArray[j-1];
	// } else if (pattern[j] != text[i]) { // mismatch after j matches
	// // Do not match lps[0..lps[j-1]] characters,
	// // they will match anyway
	// if (j != 0)
	// j = lpsArray[j - 1];
	// else
	// i = i + 1;
	// }
	// }
	// }
}